# -*- coding: utf-8 -*-
"""
Created on Sat Nov 10 00:04:59 2018

@author: Administrator
"""

# match parens
# scan a string line, the string may contain a number of parens
# the task is to check the string with matched parens

from seq_stack import SeqStack

class ParensApplication:
    
    def __init__(self):
        self.parens = "()[]{}"   # 所有的括号字符
        self.open_parens = "([{" # 所有的开括号字符
        self.matched_parens = {")" : "(", "]":"[", "}":"{"} # 括号配对字典
        
    def filter_not_parens(self, line):
        """过滤非括号的字符
        """
        result = []
        for char in line:
            if char in self.parens:
                result.append(char)
        return result
        
    def check_parens(self, line):
        ls = SeqStack()
        filtered_line = self.filter_not_parens(line)
        # 遍历字符串
        # 如果遇见左括号，入栈，非括号字符略过，遇到右括号，弹栈
        # 如果结束后栈为空，则匹配成功
        for char in filtered_line:
            if char in self.open_parens:  # 遇到左括号入栈
                ls.push(char)
            else:                         # 遇到右括号
                left = ls.pop()
                if self.matched_parens[char] != left: # 判断左右括号是否匹配
                    return False
        return True

"""计算后缀表达式的值
中缀表达式：(2 + 3) * 3
后缀表达式：23+3*
"""
class SuffixCalculator:
    
    def __init__(self):
        self.operator = "+-*/"
    
    def calculate(self, line):
        """计算后缀表达式
        """
        stack = SeqStack()
        for char in line:
            if char not in self.operator:
                stack.push(char)
            else:
                b = float(stack.pop())
                a = float(stack.pop())
                
                try:
                    temp = 0
                    if char == "+":
                        temp = a + b
                    elif char == "-":
                        temp = a - b
                    elif char == "*":
                        temp = a * b
                    else:
                        temp = a / b
                except ZeroDivisionError as e:
                    print(e.with_traceback())
                    
                stack.push(temp)
        if stack.depth() != 1:
            raise ValueError("suffix calculation error!")
        else:
            return stack.pop()
    

class InfixTransSuffix:
    
    def __init__(self):
        self.priority = {"(":1, "+":3, "-":3, "*":5, "/":5}
        self.infix_operator = "+-*/()"
    
    def trans(self, line):
        """把中缀表达式转换为后缀表达式
        中缀表达式：(2+3)*4
        后缀表达式：23+4*
        """
        stack = SeqStack() # 辅助空间，存储运算符
        exp = []
        
        for char in line:
            # 如果为( ，入栈stack
            if char == "(":
#                stack.push(char)
                continue
            elif char not in self.infix_operator:
                # 如果为操作数
                exp.append(char)
            elif char == ")": 
                # 如果为 ),依次谈栈即可
                while not stack.is_empty():
                    exp.append(stack.pop())
#                stack.pop() # stack删除"("
                
            else:
                # 如果为运算符，需要处理优先级 栈顶优先级高要优先处理，或者同级也处理（左结合）
                if (not stack.is_empty()) and self.priority[stack.top()] >= self.priority[char]:
                    exp.append(stack.pop())
                stack.push(char)
        # 如果栈还有元素，送出
        if not stack.is_empty():
            exp.append(stack.pop())
        return "".join(exp)